Les chiffrages par substitution
Le chiffrage par substitution est celui dans lequel les lettres ont été remplacées par quelque chose d'autre, selon une règle simple prédéfinie. On peut par exemple décider d'une telle correspondance :
texte clair.....abcdefghijklmnopqrstuvwxyz texte chiffré...polikujmnhytgbvfredcxswqaz
Et donc, "the" dans notre message original devient "cmk" dans le message chiffré.
Une bonne compréhension des chiffrages par substitution ainsi que de la manière de les résoudre
vous permettra de bien avancer dans les challenges.
Bien que je m'apprête à parler des substitutions monoalphabétiques, vous verrez que souvent les
épreuves de challenges sont fondées sur des chiffrages par substitution
et que, par une correspondance appropriée, on peut se ramener à un problème de substitution comme ci-dessus.
Pour ça, il suffit juste de déterminer où les lettres sont situées.
Par exemple, dans un texte chiffré composé d'un ensemble de dessins, de symboles graphiques ou d'images,
vous comptez ceux-ci et vous voyez qu'il y en a moins de 26, et qu'en outre vous avez des séquences qui se répètent,
dont certaines sont plus fréquentes que d'autres. La façon d'approcher le problème est de substituer
une lettre à chaque symbole et de traiter le tout comme un chiffrage par substitution.
Dans d'autres problèmes, vous pouvez voir qu'il existe un symbole répétitif : est-ce simplement un séparateur d'une certaine sorte ?
Représente-t-il le début d'une nouvelle lettre ou bien d'un nouveau mot ?
Gardez à l'esprit que le texte chiffré n'est pas nécessairement un autre alphabet - ça peut être un ensemble d'images, ou des nombres de trois chiffres, ou deux lettres, ou n'importe quoi d'autre à partir de quoi il vous semble qu'une correspondance vers des lettres pourrait facilement être rétablie. Quelquefois, le texte chiffré n'aura pas 26 combinaisons différentes, car un nombre inférieur peut être suffisant. Par exemple, regardez cette matrice :
--ready ------- q-abcde u-fghik i-lmnop t-qrstu s-vwxyz
Ici, on fait correspondre une lettre avec la lettre du haut de la rangée (ready) et celle de la colonne de gauche (quits), "a" devenant ainsi "rq" et "b" devenant "eq". Comme il n'y a pas de j dans le tableau, on le traite comme si c'était un "i" et on utilise "du". Ce qui est le plus parlant quand on décode un message. Pour résoudre un message ainsi chiffré, il faut comprendre que le texte chiffré possède seulement dix caractères différents et que ceux-ci sont construits sur un moule à partir d'un caractère de "ready" et un autre de "quits". Maintenant, vous pouvez construire une table de correspondance en partant de deux caractères de l'alphabet de substitution pour le remplacer ce couple par un seul caractère et vous ramener ainsi au déchiffrage de n'importe quel problème de substitution.
Maintenant, supposez un texte chiffré de ce genre et composé de lettres de a à z. Il peut inclure ou non des séparation appropriées de mots, c'est à dire qu'il peut comprendre ou non des espaces). Je vous proposerais plusieurs méthodes pour attaquer le problème :
Parlons donc de mon solveur automatique. Comment est-ce qua ça marche ? Eh bien, la première chose que j'ai faite, ça a été d'analyser tu texte anglais avec ce programme. Tout ce qu'il fait, c'est de lire un paquet de texte (je lui ai fait avaler un bon gros roman). Il ressort des fichiers contenant le comptage des différentes fréquences, à partir duquel on peut déterminer le nombre de fois où les lettres devraient apparaître dans un texte anglais classique. Il donne aussi les statistiques sur les combinaisons de deux, trois et quatre lettres. Ce sont celles de quatre lettes, les tétragrammes, que mon solveur utilise. Les autres fichiers concernent seulement l'analyse. Il est important de ne pas analyser n'importe quoi, du HTML par exemple, car les combinaisons classiques vont devenir des choses comme "html" et "brbr", ce qui ne donnera rien dans le solveur et ne vous amènera nulle part. Vous devez donc analyser un texte long et représentatif. Naturellement, ce n'est pas nécessairement de l'anglais : vous pouvez être intéressé par le néerlandais par exemple :) On a donc maintenant un fichier avec la liste des fréquences pour les groupes de quatre lettres (faites la vôtre). C'est là que le CryptoAnalyseur entre en scène. Il lit votre crypto et commence avec une solution aléatoire. Il essaie d'améliorer la solution en l'évaluant par rapport aux fréquences attendues dans le message décrypté, en utilisant le fichier de tétragrammes que nous avions généré. Quand la conjecture en cours ne peut plus être améliorée, il démarre avec une autre position aléatoire. Quant la meilleure supposition est batture, il l'indique à l'écran. Un long cryptogramme est normalement résolu assez vite, en une seconde ou deux. Si vous devez attendre plus de quelques secondes, c'est que ça n'a pas marché : il va falloir essayer autre chose à la place. Parfois, le résultat sera correct à 90% et vous n'aurez plus qu'à changer quelques lettres peu fréquentes par ci par là.
Si le programme échoue et que le mots sont séparés, alors le truc à essayer ensuite, c'est la concordance de structure. La concordance de structure signifie que si dans le texte codé vous avez un mot "dxllkdduxt", alors vos allez chercher des concordance possibles pour ce mot, c'est à dire un mot avec six lettre différentes, de longueur 10, avec une lettre qui apparaît aux places "..ll......", une aux positions ".x......x.". Perl est idéal pour ça, bien que j'aie tendance à utiliser de petits progs en C de temps en temps. Ce à quoi il faut faire attention, ce sont les structures inhabituelles dans un mot et les mots longs avec plusieurs lettres répétées, ou les mots longs avec un grand nombre de lettres différentes. Inévitablement, une concordance des structure produira seulement un petit nombre de solutions possibles à la différence d'un dico. Souvent, le mot qui constitue la réponse est évident dans le contexte du problème mais si vous obtenez un grand mot, vous aurez réussi à casser le code.
A ce stade, je prends un papier et un crayon, ou plus probablement le bloc note et je commence à réaliser quelques substitutions manuelles. Voyons donc un exemple :
juww tdru mdh zpiu fdwiut gzkf fhqfgkghgkdr skazuc prt gzu jdct gzpg mdh ruut vdc gzu prfjuc kf pwazpqug
La première chose qu'on remarque, c'est la présence de "mdh" à deux occasions, ainsi que "gzu". Le mot le plus courant dans l'anglais écrit, est "the" et nous avons donc une ouverture possible avec ces deux mots. La lettre la plus courante est le "e" et bien qu'il y ait peu de "u" dans le message codé, on pourrait avoir "gzu" = "the". Ça collerait aussi avec le "uu" dans "ruut" et le "u" en fin de mot comme "zpiu". On sait aussi que la deuxième lettre la plus fréquente en anglais est le "t" (les fréquences en anglais sont "etaonirsh...") et que le "g" est une lettre fréquente dans le message. Notons aussi que "gzpg" et "gzpg" pourraient correspondre à "th..". Tout ceci est un signe solide que "gzu" = "the". J'opère donc la substitution :
juww tdru mdh zpiu fdwiut gzkf fhqfgkghgkdr skazuc prt e e h e e th t t t he gzu jdct gzpg mdh ruut vdc gzu prfjuc kf pwazpqug the th t ee the e h et
Vous devez maintenant commencer à voir d'autres mots qui se forment. On a "gzpg" = "th.t" et oon doit donc avoir "p" = "a", seule possibilité. Ceci nous donne "pawzpqug" = "a..ha.et" et même si vous avez besoin d'effectuer une rechercher dans un dictionnaire, vous devriez rapidement trouver "alphabet". On a aussi "zpiu" = "ha.e", soit probablement "have", "prt" = "a.." et doc probablement "and", ce que confirme "ruut" = "need", etc. En effectuant ces substitutions, on obtient :
juww tdru mdh zpiu fdwiut gzkf fhqfgkghgkdr skazuc prt ell d ne have lve th b t t t n phe and gzu jdct gzpg mdh ruut vdc gzu prfjuc kf pwazpqug the that need the an e alphabet
C'est quasiment terminé. Il reste à décider que le message commence par "Well done", et que "k" = "i" et "f" = "s". En final, si vous écrivez l'alphabet en clair et l'alphabet codé, vous obtiendrez ceci :
abcdefghijklmnopqrstuvwxyz pqstuv zk w rda cfghij m
Vous remarquerez que plusieurs lettres de l'alphabet chiffré sont dans l'ordre, du fait qu'un mot clé a été utilisé. On peut ajouter que "q" = "b", "x" = "l" et puis ""z" = "n" ou "o", et "g" = "x" ou "y". Un contrôle attentif des possibilités donne l'alphabet reconstruit :
abcdefghijklmnopqrstuvwxyz pqstuvxzkeywordabcfghijlmn
Et on voit le mot clé dans l'alphabet chiffré... qui est "keyword". Les mots clés peuvent aussi apparaître Les mots clés peuvent aussi apparaître autrement, c'est à dire en écrivant l'alphabet chiffré et la correspondance avec le clair juste en dessous. Donc quand vous savez que la réponse est le mot-clé, c'est là qu'il faut regarder.
Voilà, on l'a joué "papier-crayon" avec quelques conjectures pleines d'astuce, mais quid si avec tout ça, on ne trouve la solution ? C'est le moment de faire un peu plus dur :) En premier lieu, il faut penser à l'analyse des fréquences du message codé. Naturellement, il vous faut connaître les fréquences propres à votre langue (rappelez-vous nos fichiers ... les fréquences figurent dans l'un d'eux...). Je ne vais pas vraiment aller très en profondeur, mais si vous voulez suivre cette ligne de pensée, et même des approches un peu plus complexes -identification des consonnes et des voyelles ainsi que la méthode des consonnes en ligne expliquée par Helen Fouche Gaines dans son livre "Cryptanalysis". Voilà l'essentiel que vous devriez retenir :
Voici le problème n° 50 de Helen Fouche Gaines:
pouy ibquav puko m eguhac mk koh poukh obljh, kohbcbgh gbbjhnhyk ghshunhc ma uawlgr kb bah hrh pouso smljhc iyuacahjj.
Comptage des fréquences :
a 7 b 8 c 5 d 0 e 1 f 0 g 5 h 17 i 2 j 5 k 7 l 3 m 4 n 2 o 8 p 4 q 1 r 2 s 3 t 0 u 9 v 1 w 1 x 0 y 3 z 0 98 lettres
Alors... le "h" est de loin la lettre la plus fréquente et devient donc immédiatement un candidat pour le "e". Ensuite, on a les lettres "a b k o u" avec des fréquences similaires (7-9) puis "c g j m p" juste après (4-5). La preuve que "h" = "e" se confirme avec la fin de plusieurs mots, l'avant-dernière position dans un mot et dans "hrh" = "eve" ? Jetons un coup d'oeil aux bigrammes :
hy 1 yh 1 ha 1 ah 2 hn 1 nh 2 hr 1 rh 1 hj 1 jh 3 hs 1 sh 1 uh 1 oh 2 kh 1 hb 1 gh 2 hc 2
On trouve donc fréquemment le "h" dans des bigrammes inverses et au contact d'une deux lettres à basse fréquence. Il voisine avec de nombreuses lettres et c'est donc presque certainement une voyelle. Du fait qu'on la trouve à la fin de nombreux mots, c'est presque certainement un "e". Procédons à la substitution :
pouyh ibquav puko m eguhac mk koh poukh
e e e e
obljh, kohbcbgh gbbjhnhyk ghshunhc ma uawlgr kb
e e e e e e e e
bah hrh pouso smljhc iyuacahjj.
e e e e e
Maintenant, on remarque que le premier et le huitième mots sot très similaires, "k" et "y" doivent être des consonnes et au moins une du bloc "pou" est une voyelle. Ce n'est toutefois probablement pas le "p". Le "o" se trouve à la fin d'au moins deux mots. Donc regardons plutôt le "u". Il survient aussi dans le cinquième mot juste avant notre "e" excluant de fait la possibilité d'un "a" ou d'un "o", nous laissant avec soit le "i" soit le "u". Toutefois, on a aussi un "hu"un peu plus loin dans le message chiffré, (ghshunhc), et aussi un mot commençant par "u" (uawlgr). Tout ceci, et le fait que le "u" est la deuxième lettre la plus fréquente dans le texte chiffré, tend à prouver que "u" = "i". Je suis certain qu'à ce stade, vous avez pensé au "m" isolé dans le message, qui doit correspondre au "i" ou au "a" si c'est un mot. Si nous avons déjà utilisé le "i", il ne nous reste alors que le "a". On le trouve au début de deux mots ("mk" et "ma"), ce qui est une bonne nouvelle (am, at, as etc.). En procédant à ces substitutions, on arrive donc à :
pouyh ibquav puko m eguhac mk koh poukh
i e i i a ie a e i e
obljh, kohbcbgh gbbjhnhyk ghshunhc ma uawlgr kb
e e e e e e ei e a i
bah hrh pouso smljhc iyuacahjj.
e e e i a e i e
Maintenant, portons notre attention au bigramme "kb", dont une des lettres doit être une voyelle (et j'inclus le "y" en disant cela). On a "poukh" = "..i.e" dans la première ligne ce qui écarte le "k". Comme le "b" se trouve à la fin de ce mot de deux lettres ("kb") et comme on le trouve aussi doublé dans un peu avant ("gbbjhnhyk"), ça doit vraiment être le "o". Ca nous donne toutefois une curieuse combinaison "eo". Avant le "kb", on a un mot de six lettres commençant par un "i" et dans lequel on doit avoir quelques autres voyelles. Il semble qu'une des quatre lettres "wlgr" soit bien une voyelle. Ca ne peut pas être le "g" avec un mot commençant par "gbb..." soit ".oo..." pas plus que le "r" à cause de "hrh" qui donne "e.e". On ne trouve qu'un seul "w" dans le message et est donc une possibilité. Mais le "l" montre quelques voisinages sympathiques qui pourraient en faire notre "u". Il est présent dans "obljh" = ".o..e" et dans "smljhc" = ".a..e.". En intégrant ces possibilités dans notre crypto, on arrive à :
pouyh ibquav puko m eguhac mk koh poukh i e o i i a ie a e i e obljh, kohbcbgh gbbjhnhyk ghshunhc ma uawlgr kb ou e eo o e oo e e e ei e a i u o bah hrh pouso smljhc iyuacahjj. o e e e i au e i e
On a désormais un intéressant tableau de mots et plusieurs lettres possibles qui apparaissent. Le "jj" à la fin de la crypto et le "obljh" qui donne ".ou.e" conduisent à penser que "j" = "s" ou "l", bien que le "l" soit écarté facilement. Des mots de deux lettres "mk" = "a." et "kb" = ".o", on déduit que "k" = "t", "s" ou "n", mais on a déjà utilisé le "s". On reste donc avec "n" ou "t". Il semble plus probable que "mk koh poukh" donne "at the .hite" plutôt que "an n.e ..ine". Nous pouvons donc aussi procéder à cette substitution :
pouyh ibquav puko m eguhac mk koh poukh hi e o i ith a ie at the hite obljh, kohbcbgh gbbjhnhyk ghshunhc ma uawlgr kb house theo o e oose e t e ei e a i u to bah hrh pouso smljhc iyuacahjj. o e e e hi h ause i essVous devriez maintenant voir que "p" = "w", ce qui donne les mots "with" et "white" dans le texte clair. Et vous devez maintenant pouvoir repérer "theodore roosevelt" dans la deuxième ligne. De plus, on avait déjà "white house" qui apparaissait dans le texte. On remarque que "ma" = "a." et "bah" = "o.e" qui amènent à "a" = "n" et "pouso" = "whi.h" donne "s" = "c". On a donc :
pouyh ibquav puko m eguhac mk koh poukh while o in with a riend at the white obljh, kohbcbgh gbbjhnhyk ghshunhc ma uawlgr kb house theodore roosevelt received an in ur to bah hrh pouso smljhc iyuacahjj. one e e which caused lindness
Finalement, en complétant les quelques lettres restantes avec celles qui restent à utiliser, on arrive à :
pouyh ibquav puko m eguhac mk koh poukh while boxing with a friend at the white obljh, kohbcbgh gbbjhnhyk ghshunhc ma uawlgr kb house theodore roosevelt received an injury to bah hrh pouso smljhc iyuacahjj. one eye which caused blindness
Remarquez que "hrh" = "eye", quelque chose qu'on n'avions pas envisagé parmi les possibilités de "ere" ou "eve" auxquelles j'avais rapidement abouti ;) C'est vrai que j'ai sauté à pieds joints par dessus pas mal de chose dans ce dernier exemple, dans lequel vous pourrez trouver plein d'autres choses. Il faut vraiment que vous étudiez les solutions de tous ces problèmes pour en apprécier davantage tous les points dignes d'intérêt. Après avoir lu le livre de Gaines, vous comprendrez vraiment que tout ceci n'est pas un jeu de devinette comme on pourrait le penser au premier abord.
Gaines va vous montrer comment vous pouvez vous attaquer à des problèmes difficiles dans lesquels les auteurs ont essayé de modifier la fréquence normale des lettres. Dans des problèmes plus difficiles, vous pouvez vous attendre à des choses de ce genre, comme peut-être la lettre "e" qui serait totalement absente du texte. Et soyez attentifs aux indices dans le nom du challenge :)